public class Leetcode {
}
//leetcode:931:下降路径最小和
class Solution1 {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        //因为我们是要找一个元素的下左右位置的对应的最小值，为了防止越界我们要在原数组的基础上在上左右进行扩展
        int[][] dp = new int[n+1][n+2];
        //扩展完后，由于我们要得到的是下降路径的‘最小和’，为了防止扩展位置对原数组产生影响，我们可以将左右两边的值都设置为Integer.MAX_VALUE
        for(int i = 1; i <= n; i++){
            dp[i][0] = dp[i][n+1] = Integer.MAX_VALUE;
        }
        //要找下降路径的最小和，我们就要求出数组每一个元素到最上面的最小值
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j+1], dp[i-1][j-1])) + matrix[i-1][j-1];
            }
        }
        //而我们下降路径的最小和，就是数组最后一层的几个元素到上面的最小值
        int ret = Integer.MAX_VALUE;
        for(int i = 1 ; i <= n; i++){
            ret = Math.min(ret,dp[n][i]);
        }
        return ret;
    }
}

//leetcode:64:最小路径和
class Solution2 {
    //我们想要找从左上角到右下角的路径和最小，同时每次只能向下或者向右走
    //因此我们去找这个位置的左边和上边的最小值，在加上这个位置的值就是此时这个位置的最小值
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        //为了防止越界我们要在原数组的基础上，在上边和左边扩展一层
        int[][] dp = new int[m+1][n+1];
        //因为我们是要找最小值，所以我们要将扩展后的两列值都设置为Integer.MAX_VALUE，防止对原数组产生影响
        for(int i = 0; i <= n; i++){
            dp[0][i] = Integer.MAX_VALUE;
        }
        for(int j = 0; j <= m; j++){
            dp[j][0] = Integer.MAX_VALUE;
        }
        //但是我们左上角的最小值就是它本身，因此我们要将它的的上边和左边的值设为0
        dp[0][1] = dp[1][0] = 0;
        //然后从左上角开始获得到达每个位置的最小值
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = Math.min( dp[i-1][j] , dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        //最后返回右下角的最小值
        return dp[m][n];
    }
}

//leetcode:174:地下城游戏
class Solution3 {
    //正难则反
    //我们可以去找从公主位置到骑士为值所需要的最小血量，即在某一个位置能活下来且可以往下走到最后的最小血量
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        //为了防止数据干扰，我们要将扩展的两边都设置为Integer.MAX_VALUE
        for (int i = 0; i <= n; i++) {
            dp[m][i] = Integer.MAX_VALUE;
        }
        for (int j = 0; j <= m; j++) {
            dp[j][n] = Integer.MAX_VALUE;
        }
        //因为我们要从公主位置开始得到最小血量，而我们能在公主位置处，我们至少要剩余1滴血，因此我们要保证有‘1滴血’，所以我们要将右下角的下边和右边的值设置为1，
        dp[m][n-1] = dp[m-1][n] = 1;
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >= 0; j--){
                //我们去得到下边和右边的最小值，用此时的最小值减去原数组此时的值，就能得到我们要的这个位置的最小血量
                dp[i][j] = Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                //如果我们得到的值为负数，代表这个位置是加血位置，而到达这个位置的最小血量为1即可
                dp[i][j] = Math.max(1,dp[i][j]);
            }
        }
        //最后返回其实在最开始位置所需的最小血量
        return dp[0][0];
    }
}